package day04;

import java.util.Arrays;

/**
 * @author wangzhisen
 * @Desc TODO
 * @date 2025/4/11
 */
public class QuickDemo {
    public static void main(String[] args) {
        int[] arr ={12 , 46 , 39 , 9 , 27 , 18};
        System.out.println("排序前："+Arrays.toString(arr));
        sort(arr, 0, arr.length-1);
        System.out.println("排序后："+Arrays.toString(arr));
    }

    //排序
    public static void sort(int[] arr, int left, int right) {
        if (arr==null || arr.length==0||arr.length==1){
            return;
        }
        quickSort(arr , left , right );
    }

    //快速排序
    public static void quickSort(int[] arr, int left, int right) {
        //出口
        if(left>=right){
            return;
        }
        //初始值
        int i=left;
        int j=right;
        int temp=arr[left];
        //排序
        while(i<j){
            //从右往左
            while((i<j) && arr[j]>=temp){
                j--;
            }
            //放置元素
            if(i<j){
                arr[i++]=arr[j];
            }

            //从左往右
            while((i<j) && arr[i]<=temp){
                i++;
            }
            //放置元素
            if(i<j){
                arr[j--]=arr[i];
            }

            //比较一轮
            System.out.println(Arrays.toString(arr));
        }
        //放置temp元素
        arr[i]= temp;
        //递归
        //左边数列都比temp小
        quickSort(arr, left, i-1);
        //右边数列都比temp大
        quickSort(arr, i+1, right);
    }
}
